package org.example.Soution002;

public class findMidInTwo {
    public static void main(String[] args) {
        int[] nums1=new int[]{1,2};
        int[] nums2=new int[]{3,4};
        findMidInTwo obj=new findMidInTwo();
        System.out.println(obj.findMedianSortedArrays(nums1, nums2));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //根据总数多少，获取中位数的大致位置（中位数有可能一个也有可能两个）
        int length = nums1.length+nums2.length;
        if(length%2==1){
            //说明是单数
            int mid=length/2;
            return getKthNum(nums1,nums2,mid+1);
        }else{
            //说明是双数，有两个中位数位置需要计算
            int mid=length/2-1;
            return (getKthNum(nums1,nums2,mid+1)+getKthNum(nums1,nums2,mid+2))/2;
        }

    }

    //这边需要写一个方法，找第几小的数
    public double getKthNum(int[] nums1, int[] nums2, int k) {
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;
        int index1=0,index2=0;
        int kThNum;

        while(true){
            //边界
            if(index1==nums1Length) return nums2[index2+k-1];
            if(index2==nums2Length) return nums1[index1+k-1];
            if(k==1) return Math.min(nums1[index1],nums2[index2]);
            //正常情况
            kThNum=k/2;
            int newIndex1=Math.min(index1+kThNum,nums1Length)-1;
            int newIndex2=Math.min(index2+kThNum,nums2Length)-1;
            if(nums1[newIndex1]<=nums2[newIndex2]){
                k-=newIndex1-index1+1;
                index1=newIndex1+1;
            }else{
                k-=newIndex2-index2+1;
                index2=newIndex2+1;
            }
        }
    }
}
